<?php
/**
 * 希尔排序.
 * User: Jack
 * Date: 2018/2/27
 * Time: 下午8:35
 */
function shell_sort($arr) {//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列
    for ($gap = count($arr)>>1; $gap > 0; $gap>>=1) {
        for ($i = $gap; $i < count($arr); $i++) {
            $temp = $arr[$i];
            for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap) {
                $arr[$j + $gap] = $arr[$j];
                echo "temp=$temp gap=$gap i=$i j=$j \n";
            }
            echo "\n";

            $arr[$j + $gap] = $temp;
        }
    }

    return $arr;
}

$arr = [2,3,5,4,1,6,8,7,9,0];
$arr = shell_sort($arr);
print_r($arr);